#pragma once

template<typename T>
class InsertSort
{
public:
	//void Sort(T data[], int n)
	//{
	//	for (int i = 1; i < n; ++i)
	//	{
	//		for (int j = i; j > 0; --j)
	//		{
	//			if (data[j] < data[j - 1])
	//			{
	//				swap(data[j], data[j - 1]);
	//			}
	//			else
	//			{
	//				break;
	//			}
	//		}
	//	}
	//}

	void Sort(T data[], int n)
	{
		for (int i = 1; i < n; ++i)
		{
			T e = data[i];
			int j;
			for (j = i; j > 0; --j)
			{
				if (data[j - 1] > e)
				{
					data[j] = data[j - 1];
				}
				else
				{
					break;
				}
			}
			data[j] = e;
		}
	}
};
